Most computer graphics today use rasterization or raytracing to generate images. Rasterization and raytracing are two fundamentally different graphics techniques. In rasterization, all the modelling primitives used to describe the scene are projected towards the display, and the pixels covered by each primitive are determined. A per-pixel depth test is then applied to determine which primitive is visible in each pixel. This process is described in more detail by Tomas Akenine-Möller and Eric Haines, Real-Time Rendering, (2nd Ed., 2002). The second, raytracing, works backwards from the display. In raytracing, the modeling primitive that is visible in each pixel is determined by shooting rays into the scene. This process is described in more detail by Andrew S. Glassner, Introduction to Raytracing (1989), and Matt Pharr and Greg Humphreys, Physically Based Rendering (2005).
Rasterization, currently the most widespread method for the display of interactive 3D content, is supported by hardware acceleration. Rasterization uses polygons as modelling primitives, and each object in the display is drawn on a polygon by polygon basis. Each polygon consists of a sequence of vertices, with shader attributes attached to each vertex. Each polygon is projected into the device coordinate system and the depth z(x,y) and colour c(x,y) of all points (x,y) inside each polygon are calculated from the depth and shader attributes at the vertices. To compute the colour c(x,y) of a point (x,y) on a polygon, an interpolation first over each polygon edge and a second interpolation over the row from the left to the right edge of the polygon, or some other equivalent method for interpolating attributes between vertices, is used. A shader program is then invoked to compute a colour for each point from the interpolated vertex attributes.
Each sampled point is called a fragment, and is written to an array of colour values called the frame buffer. Each value in the colour value array corresponds to a pixel on the screen. As color values are calculated and added to the array, only the colour due to the fragment closest to the eye (also referred to as the fragment having the minimum depth) is typically retained. This is accomplished by using a second array in which the depth associated with each pixel is stored. As a new colour value is calculated for a fragment, the depth of that fragment is compared to the depth associated with a given pixel. Only fragments with depths smaller than those currently in the frame buffer are allowed to update the colour and depth buffers.
Because rasterization is able to draw near real-time frames through its leveraging of specialized hardware devices, known as graphics processing units or GPU's, many programmers prefer to use rasterization in dynamically generated scenes. However, rasterization has several disadvantages. One such disadvantage is rasterization tends to produce highly local effects. That is, effects which extend beyond the context of the current polygon or pixel are difficult or impossible to compute accurately. Such effects include reflections, refractions, and indirect (global) illumination. Thus, rasterization is not as effective for generating realistic effects in some simulated environments.
More specifically, rasterization assumes an image formation process that maps straight lines in the scene to straight lines on the display. This is mathematically equivalent to stating that rasterization assumes that the projection from scene points to image points is along a set of rays which all pass through a common point. However, images formed by reflections and refractions due to curved objects, for example, do not map straight lines in the scene to straight lines in the image. Indirect illumination algorithms, in turn, may require the transport of information over many divergent paths that do not pass through a common point and so cannot be interpreted as a polygon rasterization. This is described in more detail in Philip Dutré et al., Advanced Global Illumination (2003). As a result of these shortcomings, the scenes generated by rasterization tend to look less realistic than is typically desired.
Modern graphics hardware also supports programmable shader programs. Shader programs can be invoked per fragment to convert interpolated attributes to pixel colours, as described above, or per-vertex, to support programmable projection. Graphics hardware that supports shaders typically includes a plurality of very high performance floating-point arithmetic units that allow near-simultaneous shading of many fragments or vertices. Such parallel shading techniques typically involve having all shaders execute the same instruction at once, in a single-instruction multiple-data (SIMD) mode of execution. This data-parallel computational model leads to high performance and efficient use of computational resources, but does not easily support efficient data-dependent control flow (iteration and conditional execution dependent on computed values). Nevertheless, shaders are important in high-quality rendering since they are used to simulate accurate material properties. Shaders can also read interpolated data from external arrays called texture maps. Texture maps are usually used to store images that are then pasted on surfaces, but they can be used for many other purposes, such as storage of data structures.
Raytracing is an alternative algorithm for image generation, and is described in more detail by Andrew S. Glassner, Introduction to Raytracing (1989), and Matt Pharr and Greg Humphreys, Physically Based Rendering (2005). To create an image with raytracing, for every pixel to be displayed, at least one ray is sent and followed from a virtual eye point through the pixel. The colour values of the objects hit by the appropriate ray are calculated by interpolating attributes between vertices and then invoking a shader. The result is used to determine the colours of the respective pixel.
To calculate a reflection or refraction, a new “secondary” ray is generated from the intersected surface point, and the ray tracing algorithm is called recursively. However, it should be noted that secondary rays generated from curved surfaces may not meet at a common eye point. Generally, ray tracing is much more flexible than rasterization since each ray is characterized separately with a start point and a direction. For example, for indirect illumination, we may just want to trace a set of rays to transfer information throughout a scene without an explicit image formation process. Raytracing can also easily be used to calculate accurate soft shadows, depth of field due to lens systems, glossy reflections, and other effects difficult or impossible to implement with rasterization. This is described in more detail by Robert L. Cook et al, Distributed Ray Tracing, in Proceedings of ACM SIGGRAPH 137-145 (1984), which is incorporated herein by reference in its entirety.
The fundamental operation required by raytracing is the intersection of a ray with the polygons in the scene. This is implemented by finding the first intersection point along the ray from its origin point with a specific polygon. Raytracing intersection calculations are very time intensive, since any ray might intersect any polygon in the scene. Thus, raytracing is mostly used for the generation of images where quality is the principal factor. Existing attempts at interactive ray tracing use multiple processors in massive clusters, but still do not even approximate the speed and efficiency of rasterization.